305 - Joseph/305.cpp

   1 #include <cstdlib>
   2 #include <iostream>
   3 #include <vector>
   4
   5 //#define DEBUG
   6
   7 using namespace std;
   8
   9 //retorna el minimo m para que se mueran todos los k malos antes que algún bueno
  10 int minimoM(short k){
  11     vector<short> gente;
  12     gente.reserve(28);
  13
  14
  15     int posibleM = 2;
  16
  17     while (true){
  18         //ensayar un posible m
  19         gente.clear();
  20         //Agregar el numero de personas
  21         for (short i=1; i<=2*k; i++)
  22             gente.push_back(i);
  23         int voyEn = (posibleM - 1) % gente.size();
  24         while (gente.size() > k){ //Borrar aquí la gente que va muriendo
  25             gente.erase(gente.begin() + voyEn);
  26             voyEn = (voyEn + posibleM - 1) % gente.size();
  27         }
  28         #ifdef DEBUG
  29         for (int i=0; i < gente.size(); i++)
  30             cout << gente[i] << " ";
  31         cout << endl;
  32         #endif
  33         /*cout << "ensaye posible M " << posibleM << endl;
  34         cout << "y llegue a ";
  35         for (int i=0; i < gente.size(); i++)
  36             cout << gente[i] << " ";
  37         cout << endl;*/
  38         //char c; cin >> c;
  39         if (gente[0] == 1 && gente[k-1] == k){
  40             return posibleM;
  41         }else{
  42             posibleM++;
  43         }
  44     }
  45
  46 }
  47
  48 int main(int argc, char *argv[])
  49 {
  50     //valores generados por fuerza bruta con la función de arriba
  51     //for (int i = 1; i < 14; i++) cout << i << " -> " << minimoM(i) << endl;
  52     int m[] = {0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881};
  53     int k;
  54     cin >> k;
  55     while (k > 0){
  56         cout << m[k] << endl;
  57         cin >> k;
  58     }
  59     return 0;
  60 }